<?php
/**
 * 二分查找.
 */

function binarySearch($arr, $target) {
    $len = count($arr);
    if ($len <= 1) {
        return -1;
    }

    $lower = 0;
    $high = $len - 1;

    while ($lower < $high) {
        $middle = intval(($lower + $high) / 2);

        file_put_contents("result.txt", "lower=$lower high=$high middle=$middle \n", FILE_APPEND);

        if ($arr[$middle] > $target) {
            $high = $middle;
        } else if ($arr[$middle] < $target) {
            $lower = $middle;
        } else {
            return $arr[$middle];
        }
    }
}

function binarySearchRecursive($arr, $target) {
    $len = count($arr);
    if ($len < 1) {
        return -1;
    }

    $lower = 0;
    $high = $len -1;
    $middle = intval(($lower + $high) / 2);

    file_put_contents("result.txt", "lower=$lower middle=$middle high=$high \n", FILE_APPEND);
    file_put_contents("result.txt", print_r($arr, true), FILE_APPEND);


    if ($arr[$middle] == $target) {
        return $target;
    } else if ($arr[$middle] > $target) {
        return binarySearchRecursive(array_slice($arr, 0, $middle ), $target);
    } else if ($arr[$middle] < $target) {
        return binarySearchRecursive(array_slice($arr, $middle + 1, $len - $middle), $target);
    }
}

$arr = [0,2,3,4,5,6,7,8,9];
//$search = binarySearch($arr, 8);
$search = binarySearchRecursive($arr, 2);

print_r($search);